#include <new>
#include <limits>
#include <memory.h>
#include "Buffer.h"
#include "Allocator.h"
#include "System.h"
#include "Exception.h"
#include "Log.h"

namespace illib{
	void Allocator::allocated(size_t size){
		allocated_ += size;
		if(parent_) parent_->allocated(size);
	}
	void Allocator::released(size_t size){
		allocated_ -= size;
		if(parent_) parent_->released(size);
	}
	Allocator::~Allocator(){
		if(allocated_){
			throw Exceptions::garbage;
		}
	}
	Allocator * Allocator::parent(){
		return parent_;
	}
	void Allocator::parent(Allocator *parent){
		parent_ = parent;
	}
	Allocator::Allocator(Allocator * parent) :
		parent_(parent),
		allocated_(0)
	{
	}
	Allocator * Allocator::root(){
		Allocator * parent = this;
		while(parent->parent_){
			parent = parent->parent_;
		}
		return parent;
	}

	namespace PoolAllocator{
		Pool::Pool(uint8_t* block, size_t blockSize, size_t itemSize, uint8_t alignment, Allocator * allocator) :
			Tracked(block, blockSize, this),
			Allocator(allocator),
			itemSize_(itemSize),
			data_(block_+calculateMapSize(blockSize, itemSize, alignment)),
			used_(0)
		{
			memset(block_, 0x00, mapsize());
		}

		Pool::~Pool() {
			if(used_) {
				throw Exceptions::garbage;
			}
			itemSize_ = 0;
			data_ = 0;
			used_ = 0;
		}

		void Pool::clear(){
			memset(block_, 0x00, mapsize());
			used_ = 0;
		}

		uint8_t* Pool::allocate(size_t requestedSize, size_t &allocatedSize) {
			if(requestedSize > itemSize_){
				throw Exceptions::arguments;
			}
			if(full()) return 0;
			size_t capacity_ = capacity();
			size_t i = 0;
			while(i < capacity_) {
				size_t byteIndex = i / 8;
				uint8_t bitIndex = i % 8;
				if ((reinterpret_cast<uintptr_t>(byteIndex+block_) % alignof(uintptr_t) == 0) && (bitIndex == 0) && (capacity_ - i >= sizeof(uintptr_t) * 8)){
					unsigned int value = reinterpret_cast<unsigned int *>(block_)[byteIndex];
					if(value == std::numeric_limits<uintptr_t>::max()) {
						i += sizeof(unsigned int) * 8;
						continue;
					}
				}
				bool used = (block_[byteIndex] >> bitIndex) & 0x01;
				if (!used) {
					block_[byteIndex] |= 0x01 << bitIndex;
					used_ += 1;
					allocatedSize = itemSize_;
					return data_ + (i * itemSize_);
				}
				i++;
			}
			allocatedSize = itemSize_;
			return 0;
		}

		bool Pool::release(void* ptr) {
			if (!contains(ptr))
				return false;
			uint8_t *start = static_cast<uint8_t*> (ptr);
			size_t index = static_cast<size_t> (start - data_) / itemSize_;
			size_t byteIndex = index / 8;
			uint8_t bitIndex = index % 8;
			bool used = (block_[byteIndex] >> bitIndex) & 0x01;
			if (!used)
				return false;
			block_[byteIndex] &= ~(0x01 << bitIndex);
			used_ -= 1;
			memset(data_ + (index * itemSize_), 0xaa, itemSize_);
			return true;
		}

		bool Pool::contains(void* ptr) {
			size_t capacity_ = capacity();
			uint8_t* end = static_cast<uint8_t*> (ptr) + itemSize_;
			if (ptr < data_)
				return false;
			if (end > data_+(capacity_*itemSize_))
				return false;
			return true;
		}

		size_t Pool::calculateMemorySize(size_t itemSize, size_t itemCount, uint8_t alignment){
			if(itemSize == 0) throw Exceptions::arguments;
			if(itemCount == 0) throw Exceptions::arguments;
			size_t mapSize;
			if(itemCount % 8 == 0) mapSize = ((itemCount) >> 3);
			else mapSize = ((itemCount) >> 3) + 1;
			size_t blockSize = (itemSize * itemCount) + System::align(mapSize, alignment);
			return blockSize;
		}

		size_t Pool::calculateItemCount(size_t blockSize, size_t itemSize, uint8_t alignment){
			if(itemSize == 0) throw Exceptions::arguments;
			if(blockSize == 0) throw Exceptions::arguments;
			size_t itemCount = (blockSize / itemSize)+1;
			size_t calculatedBlockSize = calculateMemorySize(itemSize, itemCount, alignment);
			while(calculatedBlockSize > blockSize) {
				itemCount--;
				if(itemCount == 0) throw Exceptions::arguments;
				calculatedBlockSize = calculateMemorySize(itemSize, itemCount, alignment);

			}
			return itemCount;
		}

		size_t Pool::calculateMapSize(size_t blockSize, size_t itemSize, uint8_t alignment){
			size_t itemCount = calculateItemCount(blockSize, itemSize, alignment);
			size_t mapSize;
			if(itemCount % 8 == 0) mapSize = ((itemCount) >> 3);
			else mapSize = ((itemCount) >> 3) + 1;
			return System::align(mapSize, alignment);
		}

		size_t Pool::allocated(){
			return itemSize_;
		}

		size_t Pool::used(){
			return used_;
		}
		size_t Pool::avaliable(){
			return capacity() - used_;
		}
		size_t Pool::capacity(){
			return (blockSize_ - mapsize())/itemSize_;
		}
		size_t Pool::mapsize(){
			return data_ - block_;
		}
		bool Pool::empty(){
			return used_ == 0;
		}
		bool Pool::full(){
			return capacity() == used_;
		}
		const char * Pool::name(){
			return TN(PoolAllocator::Pool);
		}

		ManagedPool::ManagedPool(uint8_t* block, size_t blockSize, size_t itemSize, uint8_t alignment, BasicAllocator * parent) :
			Pool(block, blockSize, itemSize, alignment, parent)
		{
		}
		ManagedPool::~ManagedPool(){
		}

		const char * ManagedPool::name(){
			return TN(PoolAllocator::ManagedPool);
		}


		BasicAllocator::BasicAllocator(size_t itemSize, size_t poolSize, uint8_t alignment, Allocator * parent) :
			Allocator(parent),
			itemSize_(itemSize),
			poolSize_(poolSize),
			alignment_(alignment)
		{
		}
		BasicAllocator::~BasicAllocator(){
			BasicLinkedList::Iterator i(pools_);
			// Search for a non full pool
			while(i.current()){
				ManagedPool* pool = static_cast<ManagedPool*>(i.current());
				if(pool->used()) {
					ConsoleLogger console(0, "\n", " ");
					throw Exceptions::garbage;
				}
				pools_.remove(i);
				destroyPool(*pool);
				i.next();
			}
		}
		bool BasicAllocator::release(void* ptr){
			throw Exceptions::unimplemented;
		}
		size_t BasicAllocator::itemSize(){
			return itemSize_;
		}
		size_t BasicAllocator::poolSize(){
			return poolSize_;
		}

		const char * BasicAllocator::name(){
			return TN(PoolAllocator::BasicAllocator);
		}

		ManagedPool& BasicAllocator::createPool(){
			size_t dataSize =  poolSize_ - sizeof(ManagedPool);
			uint8_t* memory = System::allocator().allocate(poolSize_, alignof(ManagedPool));
			allocated(poolSize_);
			uint8_t* poolMemory = memory+sizeof(ManagedPool);
			//if(reinterpret_cast<uintptr_t>(poolMemory) % ) throw Exceptions::alignment;
			if(reinterpret_cast<uintptr_t>(memory) % alignof(ManagedPool)) throw Exceptions::alignment;
			ManagedPool & pool = *new(memory)ManagedPool(poolMemory, dataSize, itemSize_, alignment_, this);
			return pool;
		}

		void BasicAllocator::destroyPool(ManagedPool& pool){
			MemoryTracker::Tracked * entry = MemoryTracker::tracker().entry(pool.start());
			assert(entry);
			assert(MemoryTracker::tracker().untrack(*entry));
			size_t size = pool.size() + sizeof(ManagedPool);
			pool.~ManagedPool();
			System::allocator().release(&pool, size);
			released(size);
		}

		void BasicAllocator::clear(){
			BasicLinkedList::Iterator i(pools_);
			while(pools_.length()){
				ManagedPool* pool = static_cast<ManagedPool*>(pools_.head());
				pools_.remove(*pools_.head());
				pool->clear();
				destroyPool(*pool);
			}
		}

		uint8_t* BasicAllocator::allocate(size_t requestedSize, size_t & allocatedSize){
			BasicLinkedList::Iterator i(pools_);
			// Search for a non full pool
			while(i.current()){
				ManagedPool* pool = static_cast<ManagedPool*>(i.current());
				if (!pool->full())  return pool->allocate(requestedSize, allocatedSize);
				i.next();
			}
			//No pool available, create one
			ManagedPool& pool = createPool();
			pools_.add(pool, 0);
			assert(MemoryTracker::tracker().track(pool));
			return pool.allocate(requestedSize, allocatedSize);
		}

		void BasicAllocator::compact(){
			BasicLinkedList::Iterator i(pools_);
			// Search for empty pools and destroy them
			while(i.current()){
				ManagedPool* pool = static_cast<ManagedPool*>(i.current());
				if(pool->empty()){
					pools_.remove(i);
					destroyPool(*pool);
				}
				i.next();
			}
		}
	};

	namespace BlockAllocator{
		SmallBlockPoolAllocator::SmallBlockPoolAllocator(size_t itemSize, size_t poolSize, uint8_t alignment, Allocator * parent) :
			BasicAllocator(itemSize, poolSize, alignment, parent)
		{
		}
		SmallBlockPoolAllocator::~SmallBlockPoolAllocator(){
		}
		const char * SmallBlockPoolAllocator::name(){
			return TN(BlockAllocator::SmallBlockPoolAllocator);
		}
		LargeBlockTracker::LargeBlockTracker(uint8_t * block, size_t blockSize, Allocator * allocator) :
			Tracked(block, blockSize, allocator)
		{
		}
		LargeBlockTracker::~LargeBlockTracker(){
		}

		size_t LargeBlockTracker::allocated(){
			return this->Memory::size();
		}
		const char * LargeBlockTracker::name(){
			return TN(BlockAllocator::LargeBlockTracker);
		}
		SmallBlockPoolAllocatorSizeTree::SmallBlockPoolAllocatorSizeTree(){

		}

		bool SmallBlockPoolAllocatorSizeTreeFunctions::lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			SmallBlockPoolAllocator * leftAllocator = static_cast<SmallBlockPoolAllocator*>(&left);
			SmallBlockPoolAllocator * rightAllocator = static_cast<SmallBlockPoolAllocator*>(&right);
			bool result = leftAllocator->itemSize() < rightAllocator->itemSize();
			return result;
		}
		bool SmallBlockPoolAllocatorSizeTreeFunctions::greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			SmallBlockPoolAllocator * leftAllocator = static_cast<SmallBlockPoolAllocator*>(&left);
			SmallBlockPoolAllocator * rightAllocator = static_cast<SmallBlockPoolAllocator*>(&right);
			bool result = leftAllocator->itemSize() > rightAllocator->itemSize();
			return result;
		}
		bool SmallBlockPoolAllocatorSizeTreeFunctions::equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			SmallBlockPoolAllocator * leftAllocator = static_cast<SmallBlockPoolAllocator*>(&left);
			SmallBlockPoolAllocator * rightAllocator = static_cast<SmallBlockPoolAllocator*>(&right);
			bool result = leftAllocator->itemSize()  ==  rightAllocator->itemSize();
			return result;
		}
		bool LargeBlockSizeTreeFunctions::lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			LargeBlockTracker * leftChunk = static_cast<LargeBlockTracker*>(&left);
			LargeBlockTracker * rightChunk = static_cast<LargeBlockTracker*>(&right);
			bool result = leftChunk->size() < rightChunk->size();
			return result;
		}
		bool LargeBlockSizeTreeFunctions::greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			LargeBlockTracker * leftChunk = static_cast<LargeBlockTracker*>(&left);
			LargeBlockTracker * rightChunk = static_cast<LargeBlockTracker*>(&right);
			bool result = leftChunk->size() > rightChunk->size();
			return result;
		}
		bool LargeBlockSizeTreeFunctions::equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			LargeBlockTracker * leftChunk = static_cast<LargeBlockTracker*>(&left);
			LargeBlockTracker * rightChunk = static_cast<LargeBlockTracker*>(&right);
			bool result = leftChunk->size() == rightChunk->size();
			return result;
		}
		LargeBlockSizeTree::LargeBlockSizeTree(){

		}

		BasicAllocator::~BasicAllocator(){
			{
				LargeBlockSizeTreeFunctions functions;
				BasicRedBlackTree::Iterator i(freeLargeBlockTrackers_, functions);
				while(i.current()){
					LargeBlockTracker * chunk = static_cast<LargeBlockTracker *>(i.current());
					i.next();
					freeLargeBlockTrackers_.remove(*chunk);
					destroyLargeBlock(*chunk);
				}
			}
			{
				SmallBlockPoolAllocatorSizeTreeFunctions functions;
				BasicRedBlackTree::Iterator i(smallBlockPoolAllocatorSizeTree_, functions);
				while(i.current()){
					SmallBlockPoolAllocator * allocator = static_cast<SmallBlockPoolAllocator *>(i.current());
					i.next();
					smallBlockPoolAllocatorSizeTree_.remove(*allocator);
					destroySmallBlockPoolAllocator(*allocator);
				}
			}
			smallBlockPoolAllocatorAllocator.compact();
		}

		bool BasicAllocator::release(void * p){
			MemoryTracker::Tracked * entry = MemoryTracker::tracker().entry(p);
			assert(entry);
			assert(MemoryTracker::tracker().untrack(*entry));
			LargeBlockTracker * largeBlockTracker = static_cast<LargeBlockTracker *>(entry);
			LargeBlockSizeTreeFunctions functions;
			freeLargeBlockTrackers_.add(*largeBlockTracker, functions);
			memset(largeBlockTracker->start(), 0xbb, largeBlockTracker->size());
			return true;
		}

		SmallBlockPoolAllocator& BasicAllocator::newSmallBlockPoolAllocator(size_t itemSize, size_t poolSize, uint8_t alignment){
			size_t size;
			void* block = smallBlockPoolAllocatorAllocator.allocate(sizeof(SmallBlockPoolAllocator), size);
			if(reinterpret_cast<uintptr_t>(block) % alignof(SmallBlockPoolAllocator)) throw Exceptions::alignment;
			SmallBlockPoolAllocator & allocator = *new(block)SmallBlockPoolAllocator(itemSize, poolSize, alignment, this);
			allocator.parent(this);
			return allocator;
		}

		LargeBlockTracker & BasicAllocator::newLargeBlock(size_t chunkSize, size_t &allocatedSize, uint8_t alignment){
			size_t pages;
			size_t dataSize = chunkSize;
			if(dataSize % System::allocator().pagesize() == 0) pages = dataSize/System::allocator().pagesize();
			else pages = chunkSize/System::allocator().pagesize() + 1;
			size_t allocationSize = pages * System::allocator().pagesize();
			uint8_t* data = System::allocator().allocate(allocationSize, alignment);
			allocated(allocationSize);
			uint8_t * memory = largeBlockTrackerAllocator.allocate(sizeof(LargeBlockTracker), allocatedSize);
			if(reinterpret_cast<uintptr_t>(memory) % alignof(LargeBlockTracker)) throw Exceptions::alignment;
			LargeBlockTracker & chunk = *new(memory)LargeBlockTracker(data, (allocationSize), this);
			return chunk;
		}

		void BasicAllocator::destroySmallBlockPoolAllocator(SmallBlockPoolAllocator& poolAllocator){
			poolAllocator.~SmallBlockPoolAllocator();
			MemoryTracker::Tracked *entry = MemoryTracker::tracker().entry(&poolAllocator);
			assert(entry);
			assert(entry->allocator());
			assert(entry->allocator()->release(&poolAllocator));
		}

		void BasicAllocator::destroyLargeBlock(LargeBlockTracker& chunk){
			System::allocator().release(chunk.start(), chunk.size());
			released(chunk.size());
			chunk.~LargeBlockTracker();
			MemoryTracker::Tracked * entry = MemoryTracker::tracker().entry(&chunk);
			assert(entry);
			assert(entry->allocator());
			assert(entry->allocator()->release(&chunk));
		}


		BasicAllocator::BasicAllocator(uint8_t alignment, Allocator * parent) :
			Allocator(parent),
			smallBlockPoolAllocatorAllocator(sizeof(SmallBlockPoolAllocator), System::allocator().pagesize(), alignof(SmallBlockPoolAllocator), this),
			largeBlockTrackerAllocator(sizeof(LargeBlockTracker), System::allocator().pagesize(), alignof(LargeBlockTracker), this),
			alignment_(alignment)
		{
			size_t naturalSize = minimumSmallBlockSize;
			size_t pages = 1;
			size_t iterations = 0;
			size_t poolAllocators = 0;
			size_t poolSize = 0;
			while(poolAllocators < smallBlockPoolAllocatorCount){
				poolSize = (System::allocator().pagesize() * pages) - sizeof(PoolAllocator::ManagedPool);
				while(naturalSize < poolSize){
					size_t minimumWaste = 0-1;
					size_t minimumWasteItemSize;
					size_t minimumWasteItemCount;
					for(size_t step = 0; step < (naturalSize >> 2); step += 1){
						iterations++;
						size_t itemSize = System::align(naturalSize - (naturalSize >> 3) + step, alignment);
						size_t itemCount = PoolAllocator::Pool::calculateItemCount(poolSize, itemSize, alignment);
						size_t waste = poolSize - PoolAllocator::Pool::calculateMemorySize(itemSize, itemCount, alignment);
						if(waste < minimumWaste){
							minimumWaste = waste;
							minimumWasteItemSize = itemSize;
							minimumWasteItemCount = itemCount;
						}
						if(waste == 0) break;
					}
					naturalSize <<= 1;
					if(minimumWaste > sizeof(void *)) {
						continue;
					}
					SmallBlockPoolAllocator &allocator = newSmallBlockPoolAllocator(minimumWasteItemSize, poolSize+sizeof(PoolAllocator::ManagedPool), alignment);
					SmallBlockPoolAllocatorSizeTreeFunctions functions;
					smallBlockPoolAllocatorSizeTree_.add(allocator, functions);
					poolAllocators++;
					maximumSmallBlockSize_ = minimumWasteItemSize;
				}
				pages++;
			}
		}

		uint8_t * BasicAllocator::allocate(size_t requestedSize, size_t &allocatedSize){
			if(requestedSize <= maximumSmallBlockSize_){
				SmallBlockPoolAllocator requested(requestedSize, 0, 0, 0);
				SmallBlockPoolAllocatorSizeTreeFunctions functions;
				BasicRedBlackTree::Iterator i(requested, smallBlockPoolAllocatorSizeTree_.max(), smallBlockPoolAllocatorSizeTree_, functions);
				assert(i.current());
				SmallBlockPoolAllocator * pool = static_cast<SmallBlockPoolAllocator*>(i.current());
				uint8_t * data = pool->allocate(requestedSize, allocatedSize);
				return data;
			}
			LargeBlockTracker requested(0, requestedSize, 0);
			LargeBlockSizeTreeFunctions functions;
			BasicRedBlackTree::Iterator i(requested, freeLargeBlockTrackers_.max(), freeLargeBlockTrackers_, functions);
			LargeBlockTracker * chunk = static_cast<LargeBlockTracker *>(i.current());
			if(chunk != 0){
				freeLargeBlockTrackers_.remove(*chunk);
				allocatedSize = chunk->allocated();
				assert(MemoryTracker::tracker().track(*chunk));
				return chunk->start();
			}
			size_t largeBlockTrackerAllocatedSize;
			LargeBlockTracker & allocated = newLargeBlock(requestedSize, largeBlockTrackerAllocatedSize, alignment_);
			allocatedSize = allocated.size();
			assert(MemoryTracker::tracker().track(allocated));
			return allocated.start();
		}
		void BasicAllocator::compact(){
			{
				SmallBlockPoolAllocatorSizeTreeFunctions functions;
				BasicRedBlackTree::Iterator i(smallBlockPoolAllocatorSizeTree_, functions);
				while(i.current()){
					SmallBlockPoolAllocator * poolAllocator = static_cast<SmallBlockPoolAllocator *>(i.current());
					poolAllocator->compact();
					i.next();
				}
			}
			{
				LargeBlockSizeTreeFunctions functions;
				BasicRedBlackTree::Iterator i(freeLargeBlockTrackers_, functions);
				while(i.current()){
					LargeBlockTracker * chunk = static_cast<LargeBlockTracker *>(i.current());
					i.next();
					freeLargeBlockTrackers_.remove(*chunk);
					destroyLargeBlock(*chunk);
				}
			}
		}
		void BasicAllocator::clear(){
			throw Exceptions::unimplemented;
			/*BasicLinkedListIterator i(poolsAllocators_.head());
			while(i.current()){
				BufferAllocatorManagedPoolAllocator * poolAllocator = static_cast<BufferAllocatorManagedPoolAllocator *>(i.current());
				poolAllocator->clear();
				i.next();
			}
			i.current(freeChunks_.head());
			while(i.current()){
				BufferAllocatorManagedChunk * chunk = static_cast<BufferAllocatorManagedChunk *>(i.current());
				destroyChunk(chunk);
				i.next();
			}
			freeChunks_.clear();
			i.current(allocatedChunks_.head());
			while(i.current()){
				BufferAllocatorManagedChunk * chunk = static_cast<BufferAllocatorManagedChunk *>(i.current());
				destroyChunk(chunk);
				i.next();
			}
			allocatedChunks_.clear();*/
		}
		const char * BasicAllocator::name(){
			return TN(BlockAllocator::BasicAllocator);
		}

	}
	namespace MemoryTracker{
		Tracker * Tracker::instance_;
		Tracker & tracker(){
			return *Tracker::instance_;
		}
		void tracker(Tracker & tracker){
			Tracker::instance_ = & tracker;
		}
		Tracked::Tracked(uint8_t* block, size_t blockSize, Allocator * allocator) :
			Memory(block, blockSize),
			allocator_(allocator)
		{
		}
		Tracked::~Tracked(){
		}
		Allocator * Tracked::allocator(){
			return allocator_;
		}
		bool Tracker::empty(){
			return tracked_.length() == 0;
		}
		Tracker::Tracker(){
			instance_ = this;
			unsigned int top_;
			void * top = &top_;
			if (top > this) stackDirection_ = true;
			else stackDirection_ = false;
		}
		bool Tracker::stack(void * ptr){
			unsigned int top_;
			void * top = &top_;
			if (stackDirection_ && ptr > instance_ && ptr < top) return true;
			else if (ptr < instance_ && ptr > top) return true;
			return false;
		}
		bool Tracker::release(void * ptr){
			MemoryTracker::Tracked * entry = instance_->entry(ptr);
			if(!entry) return false;
			if(!entry->allocator()) return false;
			if(!entry->allocator()->release(ptr)) return false;
			return true;
		}
		size_t Tracker::length(){
			return tracked_.length();
		}


		DummyTracked::DummyTracked(uint8_t * ptr, size_t size) :
				Tracked(ptr, size, 0)
		{
		}
		DummyTracked::~DummyTracked(){
		}

		size_t DummyTracked::allocated(){
			throw Exceptions::unimplemented;
		}
		const char * DummyTracked::name(){
			return TN(DummyTracked);
		}
		bool Tracker::track(Tracked & memory){
			if(entry(memory.start())) return false;
			MemoryTreeFunctions functions;
			tracked_.add(memory, functions);
			return true;
		}

		bool Tracker::untrack(Tracked & memory){
			MemoryTreeFunctions functions;
			BasicRedBlackTree::Iterator i(memory, tracked_, functions);
			if(!i.current()) return false;
			tracked_.remove(*i.current());
			return true;
		}

		Tracked * Tracker::entry(void * ptr){
			DummyTracked target(reinterpret_cast<uint8_t*>(ptr), 0);
			MemoryTreeFunctions functions;
			BasicRedBlackTree::Iterator i(target, tracked_, functions);
			return static_cast<Tracked*>(i.current());
		}

		bool MemoryTreeFunctions::lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			Tracked * leftEntry = static_cast<Tracked*>(&left);
			Tracked * rightEntry = static_cast<Tracked*>(&right);
			bool result = (leftEntry->start() < rightEntry->start()) && (leftEntry->end() < rightEntry->end());
			return result;
		}

		bool MemoryTreeFunctions::greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			Tracked * leftEntry = static_cast<Tracked*>(&left);
			Tracked * rightEntry = static_cast<Tracked*>(&right);
			bool result = (leftEntry->start() > rightEntry->end());
			return result;
		}

		bool MemoryTreeFunctions::equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			Tracked * leftEntry = static_cast<Tracked*>(&left);
			Tracked * rightEntry = static_cast<Tracked*>(&right);
			bool result = (leftEntry->start() >= rightEntry->start()) && (leftEntry->end() <= rightEntry->end());
			return result;
		}
		MemoryTree::MemoryTree(){

		}
	}
};
